// 28. 找出字符串中第一个匹配项的下标

#include <string>
using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) 
    {
        int i = 0; // 维护每一次haystack字符串开始的位置，同时为下一次从头走做记录
        int left1 = 0, left2 = 0, right1 = haystack.size(), right2 = needle.size();
        for( ; left1 < right1 && left2 < right2; left1++, left2++)
        {
            if(haystack[left1] != needle[left2])
            {
                left2 = -1; // 将 needle 的做指针置头位置，因为循环调整有++所以维护为-1
                left1 = i; // 同上，因为++，所以i开始设为0
                i++; // 标记 haystack 字符串开始的位置
            }
        }
        if(left2 == right2) return i; // i 记录了头位置，直接返回
        return -1;
    }
};